337. 打家劫舍 III

#leetcode/dp/iteration #leetcode/recursive/memo #leetcode/tree/traversal/sub-tree #leetcode/unsolved

337. 打家劫舍 III

Similar Question

树形DP如何思考？打家劫舍III_哔哩哔哩_bilibili

Solution Tips

方案一: 记忆化搜索 + 递归

在解法一和解法二中，我们使用爷爷、两个孩子、4 个孙子来说明问题

首先来定义这个问题的状态, 爷爷节点如何获取到最大的偷取的钱数呢

  1. 首先要明确相邻的节点不能偷，也就是爷爷选择偷，儿子就不能偷了，但是孙子可以偷
  2. 二叉树只有左右两个孩子，一个爷爷最多 2 个儿子，4 个孙子

根据以上条件，我们可以得出单个节点的钱该怎么算, 4 个孙子偷的钱 + 爷爷的钱 VS 两个儿子偷的钱 哪个组合钱多，就当做当前节点能偷的最大钱数。这其实就是动态规划里面的最优子结构

由于是二叉树，这里可以选择计算所有子节点

挑选一个钱数多的方案则

int result = Math.max(method1, method2);

因为偷儿子的钱的时候, 也会去计算孙子的钱, 所以需要先计算偷儿子的. 如果先计算偷孙子的, 就还是会有很多重复的计算, 因为在计算儿子的时候, 孙子的值也还没有记录下来


const memo = new Map();

var rob = function(root) {
    // 从叶子节点开始偷窃, 似乎是最好的, 那样可以从 root 获取答案

    if (root === null) return 0;

    // const [left, leftSun] = dfs(node.left);
    // const [right, rightSun] = dfs(node.right);
    // 好像没有办法获取到, 子子的值呀, node.val 应该要加上孙子的 val 才行
    // dp 也不好定义, 难搞了, 这个时候只有两种方案: 一种是暴力回溯, 一种是从dp的本质出发重新思考问题
    // return Math.max(node.val, leftRob + rightRob);
    // return [node.val, leftRob + rightRob];
    // 感觉 dp 方案走不通了, 还是参考之前贪心算法装监视器的方案, 用回溯处理吧
    if (memo.has(root)) return memo.get(root);

    const notChose = rob(root.left) + rob(root.right);
    // 选取当前节点后, 只能从孙子手上拿钱了
    let money = root.val;
    if (root.left != null) {
        money += (rob(root.left.left) + rob(root.left.right));
    }

    if (root.right != null) {
        money += (rob(root.right.left) + rob(root.right.right));
    }

    // 与不取当前节点的情况做对比, 选择更大的那个
    const res =  Math.max(money, notChose);
    // 记忆最优的结果
    memo.set(root, res)
    return res;
};

方案二: 动态规划

上面的解法用到了孙子节点，计算爷爷节点能偷的钱还要同时去计算孙子节点投的钱，虽然有了记忆化，但是还是有性能损耗。

我们换一种办法来定义此问题

每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷

我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷，1 代表偷

任何一个节点能偷到的最大钱的状态可以定义为

表示为公式如下

root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + Math.max(rob(root.right)[0], rob(root.right)[1])

root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;

const rob = root => {
    // 后序遍历函数
    const postOrder = node => {
        // 递归出口
        if (!node) return [0, 0];
        // 遍历左子树
        const left = postOrder(node.left);
        // 遍历右子树
        const right = postOrder(node.right);
        // 不偷当前节点，左右子节点都可以偷或不偷，取最大值
        const DoNot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷当前节点，左右子节点只能不偷
        const Do = node.val + left[0] + right[0];
        // [不偷，偷]
        return [DoNot, Do];
    };
    const res = postOrder(root);
    // 返回最大值
    return Math.max(...res);
};